package lanQiaoBei.基础算法.sort;
import java.io.*;
import java.lang.*;

/*
* “逆序对的数量” 3 2 1 ->3 2- 3 1- 2 1都是逆序对
给定一个长度为 n 的整数数列，请你计算数列中的逆序对的数量。

逆序对的定义如下：对于数列的第 i 个和第 j 个元素，如果满足 i<j 且 a[i]>a[j]，则其为一个逆序对；否则不是。

输入格式

第一行包含整数 n，表示数列的长度。

第二行包含 n 个整数，表示整个数列。

输出格式

输出一个整数，表示逆序对的个数。

数据范围

1≤n≤100000，
数列中的元素的取值范围 [1,109]。

输入样例：

6
2 3 4 5 6 1
输出样例：
5
* */
public class P6 {
    static int N;
    static long R;
    static int[]temp=new int[100000];
    public static void main(String[]args)throws Exception{
        int[] arr = scan();
        merger_sort(0,N-1,arr);
        System.out.println(R);
    }

    private static void merger_sort(int l, int r, int[] arr){
            if(l>=r)return;
            int mid=l+r>>1;
            merger_sort(l,mid,arr);
            merger_sort(mid+1,r,arr);
            int k=0,i=l,j=mid+1;
            while(i<=mid&&j<=r){
                 if(arr[i]<=arr[j])temp[k++]=arr[i++];
                 else{
                     temp[k++]=arr[j++];
                     R+=mid-i+1;
                 }
            }
            while(i<=mid)
                temp[k++]=arr[i++];
            while(j<=r)
                temp[k++]=arr[j++];
            for(i=l,j=0;i<r;i++,j++)
                arr[i]=temp[j];
    }

    public static int[] scan() throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
          N=Integer.parseInt(br.readLine());
          int[]arr=new int[N];
          String[]s=br.readLine().split(" ");
          for (int i = 0; i <s.length ; i++) {
              arr[i]=Integer.parseInt(s[i]);
          }
          return arr;
    }
}
